package DynamicProgrammingPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class minCostClimbingStairs_ {
  public static void main(String[] args) {
    int[] cost = new int[]{10,15,20};
    System.out.println(minCostClimbingStairs(cost));
  }

  // 1. dp[i]表示到达第i个台阶需要消耗dp[i]
  // 2. 递推公式: dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]),
  // 到达第i个台阶可以通过从第i - 1个台阶跳一个, 消耗cost[i - 1]或者从第i - 2个台阶跳两个, 消耗cost[i - 2]
  // 3. 遍历顺序: 从前向后
  // 4. 初始化: dp[0] = cost[0]; dp[1] = cost[1];
  public static int minCostClimbingStairs(int[] cost) {
    int[] dp = new int[cost.length + 1];
    dp[0] = 0;
    dp[1] = 0;
    for (int i = 2 ; i <= cost.length ; i ++){
      dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
    }
    return dp[cost.length];
  }
}
